#include <iostream>     // std::cout
#include <fstream>      // std::ofstream and std::ifstream
#include <vector>
#include <algorithm>
#include <stack>        // for stack
#include <queue>        // for queue
using namespace std;
template <typename T>
class bin_tree_node {
  public:
    T payload;                          // 节点负载
    bin_tree_node *left;                // 左子节点
    bin_tree_node *right;               // 右子节点

    // 节点的构造函数
    bin_tree_node(const T& value) {
        payload = value;
        left = nullptr;
        right = nullptr;
    }

    // 节点的析构函数
    ~bin_tree_node() {
        if (left)
            delete left;
        if (right)
            delete right;
    }

    // 深度优先（depth-first）前序遍历
    template <typename visitor_func>
    void dfs_preorder(visitor_func visitor, string path)
    {
        // call the visitor for the current node
        visitor(payload, path);

        if (left)
            left->dfs_preorder(visitor, path + "0");
        if (right)
            right->dfs_preorder(visitor, path + "1");
    }
};
size_t asc[128];
int main(int argc, const char* argv[]){
    string a;
    string start;
    if (argc > 1){
        start = argv[1];
        ifstream ifs;
        ifs.open(start, ifstream::in);
        while (true) {
            int c = ifs.get();
            if (c == EOF)
                break;
            if (c > 127)
                c = '?';
            asc[c]++;
        }
        ifs.close();
    }
    else{
        while (true) {
            int c = cin.get();
            if (c == EOF)
                break;
            if (c > 127)
                c = '?';
            asc[c]++;
        }
    }
    struct payload{
        int asci;
        size_t count;
        string where;
    };
    using my_bin_tree_node = bin_tree_node<struct payload>;
    vector<my_bin_tree_node*> vec;
    vector<my_bin_tree_node*> leaves;
    for(int i=0;i<128;i++){
        if(asc[i]){
            auto node = new my_bin_tree_node({i, asc[i], ""});
            vec.push_back(node);
            leaves.push_back(node);
        }
    }
    while(vec.size()>1){
        sort(vec.begin(),vec.end(),[](const my_bin_tree_node* a,const my_bin_tree_node* b)
                {
                    return a->payload.count > b->payload.count;
                });
        my_bin_tree_node* a=vec.back(); vec.pop_back();
        my_bin_tree_node* b=vec.back(); vec.pop_back();
        auto p = new my_bin_tree_node({128, a->payload.count + b->payload.count, ""});
        p->left = a;
        p->right = b;
        vec.push_back(p);
    }

    struct visitor{
        void operator() (payload& value, const string& path) {
            if (value.asci<128) {
                value.where = path;
            }
        }
    };
    vec[0]->dfs_preorder(visitor{}, "");
    cout<<endl;
    for (const auto& leaf : leaves) {
        cout<<(char)(leaf->payload.asci)<<": "<<leaf->payload.where<<endl;
    }
    /*
    struct context_print {
        bool root;
        ostream& os;
    };

    struct visitor_print {
        void operator() (const & value) {
            if (ctxt->root) {
                ctxt->os << value;
                ctxt->root = false;
            }
            else {
                ctxt->os << ", " << value;
            }
        }
    };

    context_print ctxt = { true, cout };
    clog << "DFS Traversal (preorder)\n";
    root->dfs_preorder(&ctxt, visitor_print{});
    cout << endl;
    return 0;*/
}
